package com.hot100.mid;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author zhengTao
 * @version 1.0
 * @description: 三数之和
 * @date 2022/7/31 15:14
 */
public class Demo05 {
    public static void main(String[] args) {
        int[] nums=new int[]{-1,0,1,2,-1,-4};
        List<List<Integer>> lists = threeSum(nums);
        System.out.println(lists);
        
    }

    public static List<List<Integer>> threeSum(int[] nums) {
        //最终结果的result
        List<List<Integer>>  res=new ArrayList<>();
        //先将数组排序
        Arrays.sort(nums);
        //便利数组
        for (int i = 0; i < nums.length; i++) {
            //排序遍历后某个数字已经大于0了，则后面的就不用再排序了
            if(nums[i]>0){
                return res;
            }
            //某个元素和前一个相等，直接跳过，防止重复，第一个元素除外，防止数组越界
            if(i>0&&nums[i]==nums[i-1]){
                continue;
            }else {
                int left=i+1;    //第二个元素
                int right=nums.length-1;  //第三个元素
                while (left<right){
                    int sum=nums[i]+nums[left]+nums[right];   //三数之和
                    if(sum>0){
                        //三数之和大了，右移
                        right--;
                    }else if(sum<0){
                        //三数之和小了，元素左移
                        left++;
                    }else {
                        //正好等于0,添加到结果数组
                        ArrayList<Integer> arrayList=new ArrayList<>();
                        arrayList.add(nums[i]);
                        arrayList.add(nums[left]);
                        arrayList.add(nums[right]);
                        res.add(arrayList);
                        //过滤重复的
                        while (left<right&&(nums[left]==nums[left+1])){
                            left++;
                        }
                        while (left<right&&(nums[right]==nums[right-1])){
                           right--;
                        }
                        right--;
                        left++;
                    }
                }
            }
        }
        return res;
    }

}
